package leetcode_top;


import org.junit.Test;


public class Ex116 {
    class Solution1 {
        public Node connect(Node root) {
            preOrder(root, null);
            return root;
        }

        //这是满二叉树
        public void preOrder(Node root, Node p) {
            if (root == null) {
                return;
            }
            Node parent = null;
            if (p != null) {
                if (p.left == root && p.right != null) {
                    root.next = p.right;
                    parent = p;
                } else {
                    Node cur = p.next;
                    while (cur != null) {
                        if (cur.left != null) {
                            root.next = cur.left;
                            parent = cur;
                            break;
                        } 
                        if (cur.right != null) {
                            root.next = cur.right;
                            parent = cur;
                            break;
                        }
                        cur = cur.next;
                    }              
                }
            }
            if (root.next != null){
                preOrder(root.next, parent);
            }
            
        }
    }

    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;
    
        public Node() {}
        
        public Node(int _val) {
            val = _val;
        }
    
        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };

    class Solution {
        public Node connect(Node root) {
            Node cur = root;
            if (root == null) return root;
            else if (root.left == null) {
                if (root.right == null) {
                    return root;
                } else {
                    cur = root.right;
                }
            } else {
                cur = root.left;
            }
            Node p = root;
            while (cur != null) { //满二叉树，只需要最左节点不为空，就是满的
                Node parent = p;
                while (p != null) {
                    if (cur == p.left) {
                        cur.next = p.right;
                    } else {
                        cur.next = p.next.left;
                        p = p.next;
                    }
                    cur = cur.next;
                }
                p = parent.left;
                cur = p.left;
            }

            return root;
        }

    @Test
    public void test() {
        Solution s = new Solution();
        Node root = new Node(1);
        root.left =  new Node(2);
        root.right =  new Node(3);
        root.left.left =  new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        System.out.println(s.connect(root));
    }
}


    class Solution2 {
        public Node connect1(Node root) {
            preOrder(root);
            return root;
        }

        private void preOrder(Node root) {
            if (root == null) {
                return;
            }
            Node left = root.left, right = root.right;
            while (left != null && right != null) { //满二叉树性质：左不为空，右必不为空，因此条件二可以省略
                left.next = right;
                left = left.right;
                right = right.left;
            }

            preOrder(root.left);
            preOrder(root.right);
        }
    }


    public Node connect(Node root) {
        if (root == null) return root;
        Node cur = root, p; //满二叉树性质
        while (cur.left != null) {
            p = cur;
            while (cur != null) {
                cur.left.next = cur.right;
                if (cur.next != null) {
                    cur.right.next = cur.next.left;
                }
                cur = cur.next;
            }
            cur = p.left;
        }
        return root;
    }

    @Test
    public void test() {
        Node root = new Node(1);
        root.left =  new Node(2);
        root.right =  new Node(3);
        root.left.left =  new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        System.out.println(connect(root));
    }
}